package leetcode;

import java.util.*;

/**
 * 692.前k个高频单词
 * 给定一个单词列表words和一个整数 k ，返回前k个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序
 *
 * 输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 * 输出: ["i", "love"]
 * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
 *     注意，按字母顺序 "i" 在 "love" 之前。
 */
public class Num_692 {

    //自定义类存放字符串和出现次数
    private class WordTimes {
        public String word;
        public int times;
        public WordTimes(String word, int times) {
            this.word = word;
            this.times = times;
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        //将字符串和出现频次存入map中
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        //建立基于最小堆的优先级队列
        Queue<WordTimes> queue = new PriorityQueue<>(new Comparator<WordTimes>() {
            @Override
            public int compare(WordTimes o1, WordTimes o2) {
                if(o1.times != o2.times){
                    return o1.times - o2.times;
                }else{
                    return o2.word.compareTo(o1.word);
                }
            }
        });
        //将map转为set，进行遍历
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            if(queue.size() < k){
                //直接添加
                queue.offer(new WordTimes(entry.getKey(), entry.getValue()));
            }else if(entry.getValue() > queue.peek().times ||
                    (entry.getValue() == queue.peek().times && entry.getKey().compareTo(queue.peek().word) < 0)){
                //当前元素次数 > 队首元素次数时，先弹出队首元素
                queue.poll();
                //再将当前元素入队
                queue.offer(new WordTimes(entry.getKey(), entry.getValue()));
            }
        }
        //遍历结束此时，queue中存放着前k个高频单词
        //返回的答案要求按高到低排列，而最小堆顶部是最小的元素，所以出队时头插到list中
        List<String> list = new ArrayList<>();
        while(!queue.isEmpty()){
            list.add(0,queue.poll().word);
        }
        return list;
    }
}
